Most modern computer systems include a central processing unit (CPU) and a main memory. The speed at which the CPU can decode and execute instructions and operands depends upon the rate at which the instructions and operands can be transferred from main memory to the CPU. In an attempt to reduce the time required for the CPU to obtain instructions and operands from main memory many computer systems include a cache memory between the CPU and main memory.
A cache memory is a small, high-speed buffer memory which is used to hold temporarily those portions of the contents of main memory which it is believed will be used in the near future by the CPU. The main purpose of a cache memory is to shorten the time necessary to perform memory accesses, either for data or instruction fetch. The information located in cache memory may be accessed in much less time than information located in main memory. Thus, a CPU with a cache memory needs to spend far less time waiting for instructions and operands to be fetched and/or stored.
A cache memory is made up of many blocks of one or more words of data. Each block has associated with it an address tag and other information that uniquely identifies which block of main memory it is a copy of. Each time the processor makes a memory reference, an address tag comparison is made to see if a copy of the requested data resides in the cache memory. If the desired memory block is not in the cache memory, the block is retrieved from the main memory, stored in the cache memory and supplied to the processor. An address tag is often a subset of the address bits. For example, if the computer uses 32 address bits, the tag may, in a simple implementation, consist of the upper 12 bits.
In addition to using a cache memory to retrieve data from main memory, the CPU may lo also write data into the cache memory instead of directly to the main memory. When the processor desires to write data to the memory, the cache memory makes an address tag comparison to see if the data block into which data is to be written resides in the cache memory. If the data block exists in the cache memory, the data is written into the data block in the cache memory. In many systems a data "dirty bit" for the data block is then set. The dirty bit indicates that data in the data block is dirty (i.e., has been modified), and thus before the data block is deleted from the cache memory the modified data must be written into main memory. If the data block into which data is to be written does not exist in the cache memory, the data block must be fetched into the cache memory or the data written directly into the main memory.
In normal operation there are several different actions that may be necessary to satisfy some memory reference. A memory reference is generally a load or store instruction. First, simplest, and fastest, the reference might hit in the cache. A hit is defined as when the data for a desired memory address is present in the cache being checked (there may be multiple levels of cache). A miss is defined to be a memory reference where the data for a desired memory address is not present in the cache being checked. When there is a hit in the cache, the associated memory instruction is completed without any additional processing penalty.
The slowest operation is when the memory reference misses the cache. In this instance, a long sequence of operations is initiated to bring the relevant line from main memory into the cache. When this data is returned from memory and copied into the cache, the cache is again referenced, resulting, this time, in a hit and subsequently the requested data is supplied to the processor, or the store operation completes. This requires a considerable amount of time and represents a significant processing penalty.
Often, cache memories are direct mapped. That is, an index is used to access one of a plurality of entries in the cache. The tag for the entry is then compared with the tag portion of the address to determine whether a match (a hit) has occurred.
The prior discussion is presented as an overview of the field of the invention. Cache memory systems are well known and for a general discussion of cache systems, see for example, David A. Patterson, John L. Hennessy, Computer Architecture A Quantitative Approach, Morgan Kauffman Publishers, Inc., San Mateo, Calif., 1990, pp. 404 through 423 and 454 through 464.
Since cache address tags are stored in a RAM device, there is the possibility that the RAM data can become corrupted due to the many failure modes of memory devices. To prevent catastrophic results from such a memory failure, some computer systems are designed such that all address tags have an error correcting code (ECC) associated with them. The computer reads an address tag and its associated ECC from the cache memory, then checks and corrects (if required) the address tag before the tag is used.
With CPU clock speeds now in the 130 MHZ range, the time taken to check the cache address tag represents a significant time delay in the processing process. Also, since a good cache design yields a high percentage of "hits" and errors are infrequent, the cache address tag seldom has to be corrected and the delay time through the correction circuit unnecessarily penalizes almost every memory cycle.
What is needed in the industry is a cache hit detection method and apparatus that quickly determines when a cache hit occurs without sacrificing the integrity of the cache memory system.